package Algorithm.BalancedBinaryHeap;

import java.util.Arrays;

/**
 * 平衡二叉树堆（属于完全二叉树）
 * @author chenjunjie
 * @since 2018-03-16
 */
public class BalancedBinaryHeap {

    /**
     *  queue
     *  平衡二叉堆对象,这里测试，因此选用了int类型
     *
     */
    private int[] queue = new int[20];


    public int nodeSize = 0;


    public BalancedBinaryHeap(){}

    /**
     * getMin
     * 获取平衡二叉堆中最小值，即获取树顶端节点值,在顶端没有用到0值
     * @return 一个二叉树对象
     */
    public BinaryHeap getMin(){
        return null;
    }

    /**
     * 移除最顶端节点，过程：先将最后面的一个值放到第一个节点，然后“下沉”
     */
    public void removeMin() {
        queue[1] = queue[nodeSize];
        queue[nodeSize--] = 0;
        fixDown(1);
    }

    /**
     * 二叉树节点是否为空
     * @return
     */
    boolean isEmpty() {
        return nodeSize==0;
    }


    public int getNodeSize() {
        return nodeSize;
    }

    public void setNodeSize(int nodeSize) {
        this.nodeSize = nodeSize;
    }


    public void add(int task) {
        if (nodeSize + 1 == queue.length){
            queue = Arrays.copyOf(queue, 2*queue.length);
        }
        queue[++nodeSize] = task;
        fixUp(nodeSize);
    }

    public void clear() {
        nodeSize = 0;
    }

    private void fixUp(int k) {
        while(k>1){
            int j = k >> 1;
            if(queue[j] <= queue[k]){
                break;
            }
            int temp = queue[j]; queue[j] = queue[k]; queue[k] = temp ;
            k = j;
        }

    }

    private void fixDown(int k) {
        int j;
        while((j = k << 1) <= nodeSize && j > 0){
            if(j < nodeSize && queue[j] > queue[j+1]){
                j++;
            }
            if(queue[j] >= queue[k]){
                break;
            }
            int temp = queue[j]; queue[j] = queue[k]; queue[k] = temp ;
            k = j;
        }

    }


    /**
     * 排序（思路：每次取根节点数据（当前最小值）与最后一个节点进行交换，
     * 然后将节点数减1更新节点数量，再将根节点数据“下沉”，循环进行）
     */
    private void orederQueue(){
        //int[] queue_new = new int[queue.length];
        int k = 0;
        int nodeSize_temp = nodeSize;
        int  min = queue[1];
        while(k < nodeSize_temp){
            queue[1] = queue[nodeSize];
            queue[nodeSize] = min;
            nodeSize--;
            fixDown(1);
            min = queue[1];
            k++;
        }
        nodeSize = nodeSize_temp;
    }

    public void printQueueValue(){
        printQueueValue(queue);
    }

    public void printQueueValue(int[] queue){
        for (int i=1; i<=nodeSize; i++){
            int v = queue[i];
            System.out.println(v+" ");
        }
    }



    /**
     * 测试入口
     *
     */
    public static void main(String[] args){
        BalancedBinaryHeap heap = new BalancedBinaryHeap();
        // 测试1
        heap.add(3);
        heap.add(8);
        heap.add(23);
        heap.add(17);
        heap.add(41);
        heap.add(33);
        heap.add(12);
        heap.add(35);
        heap.add(26);
        heap.printQueueValue();

        //测试2
        System.out.println("-----------------");
        heap.removeMin();
        heap.printQueueValue();

        // 测试3
        System.out.println("-----------------");
        heap.orederQueue();
        heap.printQueueValue();


    }

}
